package com.practice.util;

import java.util.ArrayList;

public class BinaryTree {
	private BinaryTreeNode m_root;
	
	public BinaryTree(BinaryTreeNode root) {
		m_root = root;
	}
	
	public BinaryTreeNode getRoot() {
		return m_root;
	}
	
	public int[] preorder() {
		ArrayList<Integer> list = new ArrayList<Integer>();
		preorder(m_root, list);
		return toArray(list);
	}
	
	private int[] toArray(ArrayList<Integer> list) {
		int[] a = new int[list.size()];
		for (int i=0; i<list.size(); i++) a[i] = list.get(i);
		return a;
	}
	
	private void preorder(BinaryTreeNode node, ArrayList<Integer> list) {
		if (node == null) return;
		list.add(node.value());
		preorder(node.left(), list);
		preorder(node.right(), list);
	}
	
	/**
	 * Convenient method to create a tree. -1 represents nil node.
	 * 
	 * @param tree
	 * @return
	 */
	public static BinaryTree createTree(int[] nodes) {
		BinaryTreeNode root = new BinaryTreeNode(null, nodes[0]);
		addNode(root, nodes, 1);
		return new BinaryTree(root);
	}
	
	private static int addNode(BinaryTreeNode parent, int[] nodes, int i) {
		if (nodes[i] != -1) {
			BinaryTreeNode left = new BinaryTreeNode(parent, nodes[i]);
			parent.addLeft(left);
			i = addNode(left, nodes, i+1);
		}
		else {
			i++;
		}
		
		if (nodes[i] != -1) {
			BinaryTreeNode right = new BinaryTreeNode(parent, nodes[i]);
			parent.addRight(right);
			i = addNode(right, nodes, i+1);
		}
		else {
			i++;
		}
		
		return i;
	}
}
